package com.bascker.algorithm.practice.tree.middle.build_tree;

import com.bascker.algorithm.base.tree.TreeNode;

/**
 * 从中序与后序遍历序列构造二叉树
 * Note: 假设树中没有重复的元素
 *
 * For example:
 *  inorder: [9,3,15,20,7]      postorder: [9,15,7,20,3]
 *     3
 *    / \
 *   9   20
 *      /  \
 *     15   7
 *
 * @author bascker
 * @apiNote from leetcode T106
 */
public class Solution {

    public TreeNode<Integer> buildTree(int[] inorder, int[] postorder) {
        // 终止条件: 当前序和中序序列长度为 0 时，说明上一层的节点是根节点
        if (inorder.length == 0 && postorder.length == 0) {
            return null;
        }

        int n = inorder.length;
        int m = postorder.length;

        // 中序的最后一个数，就是根节点
        TreeNode<Integer> root = new TreeNode<>(postorder[m - 1]);

        // 找到 inorder 中跟节点位置
        int i;
        for (i = 0; i < n; i++) {
            if (inorder[i] == root.getItem()) {
                break;
            }
        }

        // 拆分数组: 将 inorder 和 postorder 拆成左子树和右子树部分
        // i == 0 时，说明只有右子树
        if (i != 0) {
            int[] leftInorder = new int[i];
            System.arraycopy(inorder, 0, leftInorder, 0, i);

            int[] leftPostOrder = new int[i];
            System.arraycopy(postorder, 0, leftPostOrder, 0, i);

            root.setLeft(buildTree(leftInorder, leftPostOrder));
        }

        // i == n - 1 时，说明只有左子树
        if (i != n - 1) {
            int[] rightInorder = new int[n - i - 1];
            System.arraycopy(inorder, i + 1, rightInorder, 0, n - i - 1);

            int[] rightPostorder = new int[n - i - 1];
            System.arraycopy(postorder, i, rightPostorder, 0, n - i - 1);

            root.setRight(buildTree(rightInorder, rightPostorder));
        }

        return root;
    }

}
